#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <sstream>
using namespace std;

struct Node{
	int start;
	int finish;
	int friends; 
};
struct NodeComp {
	bool operator() (const Node& lhs, const Node& rhs){ return lhs.friends > rhs.friends; }
};

//can a method be differentiate by const or non-const parameter?
// f(const int) or f(int)
class ShoutterDiv1 {
public:
	int count(vector <string> s1000, vector <string> s100, vector <string> s10, vector <string> s1, 
		vector <string> t1000, vector <string> t100, vector <string> t10, vector <string> t1);
private:
	int to_int(const string& str);
	bool is_connected(vector<Node>& nodes, const vector<list<int> >& graph);
};
int ShoutterDiv1::to_int(const string& str) {
	stringstream sstr(str);
	int ret;
	sstr >> ret;
	return ret;
}

int ShoutterDiv1::count(vector <string> s1000, vector <string> s100, vector <string> s10, vector <string> s1, 
		vector <string> t1000, vector <string> t100, vector <string> t10, vector <string> t1){
			//constuct nodes
			vector<Node> nodes(0);
			for ( int i = 0; i< s1000.size(); ++i) {
				for (int j = 0; j < s1000[i].size(); ++j) {
					Node n;
					char start[5];
					start[0] = s1000[i][j];
					start[1] = s100[i][j];
					start[2] = s10[i][j];
					start[3] = s1[i][j];
					start[4] = '\0';
					n.start = to_int(string(start));

					char finish[5];
					finish[0] = t1000[i][j];
					finish[1] = t100[i][j];
					finish[2] = t10[i][j];
					finish[3] = t1[i][j];
					finish[4] = '\0';
					n.finish = to_int(string(finish));

					n.friends = 0;
					nodes.push_back(n);
				}
			}
			for ( int i = 0; i < nodes.size(); ++i ) {
				for ( int j = i+1; j < nodes.size(); ++j) {
					if ( nodes[i].start >= nodes[j].start && nodes[i].start <= nodes[j].finish ||
						 nodes[i].finish >= nodes[j].start && nodes[i].finish <= nodes[j].finish ||
						 nodes[i].start <= nodes[j].start && nodes[i].finish >= nodes[j].finish) {
							 ++nodes[i].friends;
							 ++nodes[j].friends;
					}
				}
			}
			std::sort(nodes.begin(), nodes.end(), NodeComp());
			//build adjacency matrix
			vector<vector<bool> > friends(nodes.size());
			vector<vector<bool> > posts(nodes.size());
			for ( int i = 0; i < nodes.size(); ++i ) {
				friends[i].resize(nodes.size());
				posts[i].resize(nodes.size());
			}
			for ( int i = 0; i < nodes.size(); ++i ) {
				for ( int j = 0; j < nodes.size(); ++j) {
					if ( nodes[i].start >= nodes[j].start && nodes[i].start <= nodes[j].finish ||
						 nodes[i].finish >= nodes[j].start && nodes[i].finish <= nodes[j].finish ||
						 nodes[i].start <= nodes[j].start && nodes[i].finish >= nodes[j].finish) {
							 friends[i][j] = true;
							 friends[j][i] = true;
							 posts[i][j] = true;
							 posts[j][i] = true;
					}
				}
			}
			int result = 0;
			bool updated = true;
			while (updated) {
				updated = false;
				for (int i = 0; i < nodes.size(); ++i ) {
					for (int j = 0; j < nodes.size(); ++j) {
						bool post = false;
						if ( j != i && posts[i][j] == true ) {
							for (int k = 0; k < nodes.size(); ++k) {
								if ( k != i && k != j && friends[i][k]==true && posts[k][j]==false) {
									posts[k][j] = true;
									post = true;
									updated = true;
								}
							}
						}
						if (post == true)
							++result; //i post j's intro to i's friends
					}
				}
			}
			for (int i = 0; i < nodes.size(); ++i ) 
					for (int j = 0; j < nodes.size(); ++j) 
						if (posts[i][j] == false )
							return -1;
			return result;
}

void test_srm580_600_internal (char *s1000_a[], char * s100_a[], char * s10_a[], char * s1_a[],
							   char *t1000_a[], char * t100_a[], char * t10_a[], char * t1_a[], int n) {


	vector<string> s1000(n);
	vector<string> s100(n);
	vector<string> s10(n);
	vector<string> s1(n);
	vector<string> t1000(n);
	vector<string> t100(n);
	vector<string> t10(n);
	vector<string> t1(n);

	for (int i = 0; i< s1000.size(); ++i ){
			s1000[i] = s1000_a[i];
			s100[i] = s100_a[i];
			s10[i] = s10_a[i];
			s1[i] = s1_a[i];
			t1000[i] = t1000_a[i];
			t100[i] = t100_a[i];
			t10[i] = t10_a[i];
			t1[i] = t1_a[i];
	}
	ShoutterDiv1 sd;
	int result = sd.count(s1000, s100, s10, s1, t1000, t100, t10, t1);
	std::cout << result << std::endl;
}

void test_srm580_600() {
	char * s1000_a[] = {"22", "2"};
	char * s100_a[] = {"00", "0"};
	char * s10_a[] = {"11", "1"};
	char * s1_a[] = {"21", "4"};
	char * t1000_a[] = {"22", "2"};
	char * t100_a[] = {"00", "0"};
	char * t10_a[] = {"11", "1"};
	char * t1_a[] = {"43", "6"};
	int n = sizeof(s1000_a)/sizeof(char*);
	test_srm580_600_internal(s1000_a, s100_a, s10_a, s1_a, t1000_a, t100_a, t10_a, t1_a, n);

	char * s1000_b[] = {"0000"};
	char * s100_b[] = {"0000"};
	char * s10_b[] = {"0000"};
	char * s1_b[] = {"1234"};
	char * t1000_b[] = {"0000"};
	char * t100_b[] = {"0000"};
	char * t10_b[] = {"0000"};
	char * t1_b[] = {"2345"};
	n = sizeof(s1000_b)/sizeof(char*);
	test_srm580_600_internal(s1000_b, s100_b, s10_b, s1_b, t1000_b, t100_b, t10_b, t1_b, n);

	char * s1000_c[] = {"0000000000"};
	char * s100_c[] = {"0000000000"};
	char * s10_c[] = {"0000000000"};
	char * s1_c[] = {"7626463146"};
	char * t1000_c[] = {"0000000000"};
	char * t100_c[] = {"0000000000"};
	char * t10_c[] = {"0000000000"};
	char * t1_c[] = {"9927686479"};
	n = sizeof(s1000_c)/sizeof(char*);
	test_srm580_600_internal(s1000_c, s100_c, s10_c, s1_c, t1000_c, t100_c, t10_c, t1_c, n);

	char * s1000_d[] ={"00000000000000000000000000000000000000000000000000"};
	char * s100_d[] ={"00000000000000000000000000000000000000000000000000"};
	char * s10_d[] ={"50353624751857130208544645495168271486083954769538"};
	char * s1_d[] ={"85748487990028258641117783760944852941545064635928"};
	char * t1000_d[] = {"00000000000000000000000000000000000000000000000000"};
	char * t100_d[] = {"00000000000000000000000000000000000000000000000000"};
	char * t10_d[] = {"61465744851859252308555855596388482696094965779649"};
	char * t1_d[] = {"37620749792666153778227385275518278477865684777411"};
	n = sizeof(s1000_c)/sizeof(char*);
	test_srm580_600_internal(s1000_d, s100_d, s10_d, s1_d, t1000_d, t100_d, t10_d, t1_d, n);
}